A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates generally to information processing. More particularly, the present invention relates to systems and methods for processing messages at a centralized processing node (e.g., server) according to some protocol. Even more particularly, the present invention relates to systems and methods for processing, at a server, messages for synchronizing independently modifiable user datasets, for example, for multiple users having user accounts at the server.
Increasingly, people are discovering the power of computer-based personal information managers (PIMs) for managing appointments and other personal information such as tasks (xe2x80x9cto-do""sxe2x80x9d) and addresses. Individuals employ PIMs, for example, on personal computers (PCs), handheld electronic devices, and World Wide Web servers accessed via browsers. Examples of PC-based PIMs include the Sidekick(copyright) software application, which is available from Starfish(copyright) Software, Inc. (xe2x80x9cStarfishxe2x80x9d), the present assignee. Examples of handheld-device-based PIMs include the StarTAC(copyright) clipOn Organizer device and the REX PRO(trademark) organizer devicexe2x80x94both of which include licensed technology from Starfishxe2x80x94as well as the popular Palm family of organizer devices. Examples of xe2x80x9cWeb-basedxe2x80x9d PIMs include an online PIM provided by Starfish at the World Wide Web site of truesync.com. Starfish(copyright), Sidekick(copyright), and TrueSync(copyright) are registered trademarks of Starfish. StarTAC(copyright) is a registered trademark of Motorola, Inc. of Schaumburg, Ill. Starfish is a wholly owned subsidiary of Motorola, Inc. REX(trademark) and REX PRO(trademark) are trademarks of Franklin Electronic Publishers of Burlington, N.J. Palm organizers are produced by Palm Computing, Inc., a subsidiary of 3Com Corp. of Santa Clara, Calif.
The use of PIMs is ever expanding, and it has become common for an individual person to keep multiple xe2x80x9ccopiesxe2x80x9d of the same information on separate devices. For example, a user may keep his or her appointments in a dataset (i.e., collection of data) on a desktop PC at work, in a dataset on a handheld device for use in the field, and in a dataset on a remotely-accessible server (e.g., a World Wide Web server) for use anywhere in the world. Such a user is free to change the information in any one of these datasets independently of the other datasets. By doing so, the user typically spoils the equivalence between the datasets. Therefore, the user would typically synchronize these personal datasets occasionally to bring them back into equivalence. To perform such synchronization, the user generally uses a synchronization system, for example, one that is described in commonly owned U.S. Pat. No. 5,519,606, which is hereby incorporated by reference.
In synchronizing data among datasets, speed is helpful. In particular, the amount of time that a user perceives is being spent or xe2x80x9ctied upxe2x80x9d on synchronization should be minimized. This need to minimize perceived synchronization time is especially important if the user is using a dataset that, during synchronization, is not capable of being used in an ordinary fashion (e.g., is not capable of being viewed or is not capable of being altered). Even more particularly, when the user synchronizes with a dataset that is on a remotely-accessible server, the synchronization speed should remain high even if the server is handling a large number of synchronizations per unit of time, for example, for a large number of datasets maintained by the server for a large number of users. In short, a synchronization scheme is needed that is both fast and scalable for handling large numbers of synchronizations per unit of time, especially when used for server-based synchronization. Furthermore, the integrity of synchronization should be maintained such that, for example, loss of synchronization messages in transit is properly handled. The present invention satisfies these and other needs.
One embodiment of the present invention comprises a method of synchronizing a client dataset of a synchronization client with a reference dataset of a synchronization server. In this method, a plurality of synchronization messages are received at the synchronization server from the synchronization client and the messages are queued according to a set of rules. Under these rules, if a message is a change message, a change identifier is read from the message, the change identifier is written into a change ID list, the message is placed in a queue for possible non-sequential processing, and another message is received. Also, under these rules, if a message is not a change message, the message is made available for immediate processing as an unqueued message, and the message is processed before another message is received. Also in the method, the plurality of synchronization messages is processed according to another set of rules. Under this other set of rules, if there is at least one queued message and there is no unqueued message, the next queued message is processed. If there is an unqueued message and there is no queued message, the unqueued message is processed. If there is at least one queued message and there is an unqueued message, and if processing the unqueued message requires that the reference dataset be up-to-date, then the next queued message is processed. If there is at least one queued message and there is an unqueued message, and if processing the unqueued message does not require that the reference dataset be up-to-date, then the unqueued message is processed. Also in the method, processing a change confirmation request message involves reading change identifiers from the change ID list and generating a change confirmation message.
In another embodiment of the invention, the above method further comprises the step of sending change messages to the synchronization client to indicate changes to be made to the client dataset. In another embodiment, processing a change message involves performing a conflict resolution and entering the change into a reference dataset if the change survives the conflict resolution. In another embodiment, messages are sent between the synchronization client and the synchronization server in the form of action objects. In another embodiment, a change message may comprise an update to an existing data record, an addition of a new data record or a deletion of an existing data record.
A different embodiment of the present invention involves a method for processing a plurality of synchronization messages received from a synchronization client. Here, the method comprises the steps of receiving the plurality of synchronization messages from the synchronization client and controlling the queuing of the messages according to a set of rules. Under these rules, if a message is queueable, the message is placed on a queue for possible nonsequential processing and another message is received. If a message is nonqueueable, the message is made available for immediate processing as an unqueued message and the message is processed before proceeding to receive another message. Also in the method, the plurality of synchronization messages is processed according to another set of rules. Under this set of rules, if there is at least one queued message and there is no unqueued message, the next queued message is processed. If there is an unqueued message and there is no queued message, the unqueued message is processed. If there is at least one queued message and there is an unqueued message, and if the unqueued message requires that the queue be cleared before processing the unqueued message, the next queued message is processed. If there is at least one queued message and there is an unqueued message, and if the unqueued message does not require that the queue be cleared before processing the unqueued message, the next unqueued message is processed.
In another embodiment of the invention, messages received from the synchronization client are initially placed in an input queue. In another embodiment, change messages are queueable. In another embodiment, all messages other than change messages are unqueueable. In another embodiment, the method described in the previous paragraph further comprises the steps of reading a change identifier from each change message, writing the change identifiers to a change ID list, and reading the change identifiers from the change ID list to prepare a change confirmation message. In another embodiment, processing a change message involves performing a conflict resolution and entering the change into a reference dataset if the change survives the conflict resolution.
Another embodiment of the present invention involves a synchronizer for synchronizing data records on a synchronization client with data records in a reference dataset wherein the synchronization client sends messages to the synchronizer during a synchronization process. The synchronizer comprises an input queue for initially queuing messages received from the synchronization client; a smart queue for queuing messages that are determined to be queueable; a smart queue loader for retrieving a message from the input queue and, if the message is queueable, placing the message on the smart queue and proceeding to retrieve another message from the input queue, or, if the message is not queueable, making the message available for immediate processing as an unqueued messaged and waiting until the message is processed before proceeding to retrieve another message from the input queue; and a synchronization engine for receiving messages one at a time from either the smart queue or directly from the smart queue loader, processing the synchronization messages, and making any required changes to the reference dataset, wherein the synchronization engine receives messages from the smart queue or the smart queue loader according to a set of rules. Under these rules, if there is at least one queued message and there is no unqueued message, the synchronization engine receives and processes the next queued message; if there is an unqueued message and there is no queued message, the synchronization engine receives and processes the unqueued message; if there is at least one queued message and there is an unqueued message, and if the unqueued message requires that the queue be cleared before processing the unqueued message, the synchronization engine receives and processes the next queued message; and if there is at least one queued message and there is an unqueued message, and if the unqueued message does not require that the queue be cleared before processing the unqueued message, the synchronization engine receives and processes the unqueued message.
In another embodiment, the synchronizer further comprises a listener for receiving messages from a communications channel between the synchronization client and the synchronizer, and for placing the messages into the input queue. In another embodiment, the synchronizer further comprises a smart queue unloader for retrieving messages from the smart queue and making the messages available for processing by the synchronization engine. In another embodiment, the synchronizer further comprises a change ID list, wherein, when the smart queue loader receives a change message from the synchronization client, the smart queue loader reads a change identifier from the change message and writes the change identifier into the change ID list, and wherein, when the synchronization engine receives a message requesting confirmation of received changes, the synchronization engine reads change identifiers from the change ID list and prepares a change confirmation message. In another embodiment, the synchronizer also synchronizes data records on other synchronization clients with data records in corresponding reference datasets. In another embodiment, the synchronizer works with multiple instances of each of the listener, the smart queue loader and the smart queue unloader to synchronize with multiple synchronization clients. In another embodiment, the synchronizer further comprises an output queue for queuing messages from the synchronizer server to the synchronizer client. In another embodiment, the synchronizer further comprises a writer for receiving messages from the output queue, and for placing the messages onto a communications channel between the synchronization client and the synchronizer. In another embodiment, the smart queue may be disabled, and, when the smart queue is disabled, all messages are passed directly from the smart queue loader to the synchronization engine.